package com.wtgroup.demo.leetcode.org_bytedance;

import com.wtgroup.demo.common.bean.LinkNode;
import org.junit.Test;

/**
 * 两数相加
 *
 * @author 60906
 * @date 2021/5/5 13:04
 */
public class Q_两数相加 {

    @Test
    public void foo1() {
        LinkNode a = LinkNode.toListNode(2, 4, 3);
        LinkNode b = LinkNode.toListNode(5,6,4);
        Solution exe = new Solution();
        LinkNode res = exe.addTwoNumbers(a, b);
        res.print();

        Solution_2 exe2 = new Solution_2();
        LinkNode res2 = exe2.addTwoNumbers(a, b);
        res2.print();
    }


    private class Solution {
        public LinkNode addTwoNumbers(LinkNode l1, LinkNode l2) {
            LinkNode dummyHead = new LinkNode();
            LinkNode tail = dummyHead;
            int added = 0; // 进位
            while (l1 != null || l2 != null) {
                int s = (l1 != null ? l1.value : 0) + (l2 != null ? l2.value : 0) + added;
                added = s / 10;
                tail = tail.next = new LinkNode(s % 10);
                if(l1!=null) l1 = l1.next;
                if(l2!=null) l2 = l2.next;
            }
            //!! 进位问题
            if (added>0) {
                tail.next = new LinkNode(added);
            }

            return dummyHead.next;
        }
    }

    private class Solution_2 {
        public LinkNode addTwoNumbers(LinkNode l1, LinkNode l2) {
            return func(l1, l2, 0);
        }

        private LinkNode func(LinkNode a, LinkNode b, int carry) {
            if (a==null && b==null) {
                if (carry>0) {
                    return new LinkNode(carry);
                } else {
                    return null;
                }
            }

            int sum = (a!=null?a.value :0) + (b!=null?b.value :0) + carry;
            LinkNode cur = new LinkNode(sum % 10);
            cur.next = func(a != null ? a.next : null, b != null ? b.next : null, sum / 10);
            return cur;
        }
    }

}
